<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Comparison between Functional and Imperative
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora036.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora038.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Comparison between Functional and Imperative</H2>
Character strings (of Objective CAML type <I>string</I>) and 
linked lists (of Objective CAML type <I>'a list</I>) will serve as examples to
illustrate the differences between ``functional'' and ``imperative.''<BR>
<BR>
<A NAME="toc45"></A>
<H3> The Functional Side</H3>
The function <TT>map</TT> (see page <A HREF="book-ora015.html#PF-map">??</A>) is a classic
ingredient in functional languages. In a purely functional style, it
is written:


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>map<CODE> </CODE>f<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>l<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h::q<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT>f<CODE> </CODE>h<TT>)</TT><CODE> </CODE>::<CODE> </CODE><TT>(</TT>map<CODE> </CODE>f<CODE> </CODE>q<TT>)</TT><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val map : ('a -&gt; 'b) -&gt; 'a list -&gt; 'b list = &lt;fun&gt;</CODE><BR>

</PRE>
 
It recursively constructs a list by applying <TT>f</TT> to the
elements of the list given as argument, independently specifying its
head <TT>(</TT>f<CODE> </CODE>h<TT>)</TT> and its tail <TT>(</TT>map<CODE> </CODE>f<CODE> </CODE>q<TT>)</TT>. In
particular, the program does not stipulate which of the two will be
computed first. <BR>
<BR>
Moreover, the physical representation of lists need not be known to
the programmer to write such a function. In particular, problems of
allocating and sharing data are managed implicitly by the system and
not by the programmer. An example illustrating this follows:


<PRE><BR># <B>let</B><CODE> </CODE>example<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE><CODE>"one"</CODE><CODE> </CODE>;<CODE> </CODE><CODE>"two"</CODE><CODE> </CODE>;<CODE> </CODE><CODE>"three"</CODE><CODE> </CODE><CODE>]</CODE><CODE> </CODE>;;<BR><CODE>val example : string list = ["one"; "two"; "three"]</CODE><BR># <B>let</B><CODE> </CODE>result<CODE> </CODE><CODE>=</CODE><CODE> </CODE>map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<TT>)</TT><CODE> </CODE>example<CODE> </CODE><CODE> </CODE>;;<BR><CODE>val result : string list = ["one"; "two"; "three"]</CODE><BR>

</PRE>
<BR>
<BR>
The lists <TT>example</TT> and <TT>result</TT> contain equal values:


<PRE><BR># example<CODE> </CODE><CODE>=</CODE><CODE> </CODE>result<CODE> </CODE>;;<BR><CODE>- : bool = true</CODE><BR>

</PRE>
<BR>
<BR>
These two values have exactly the same structure even though their
representation in memory is different, as one learns by using the test
for physical equality:


<PRE><BR># example<CODE> </CODE><CODE>==</CODE><CODE> </CODE>result<CODE> </CODE>;;<BR><CODE>- : bool = false</CODE><BR># <TT>(</TT>List.tl<CODE> </CODE>example<TT>)</TT><CODE> </CODE><CODE>==</CODE><CODE> </CODE><TT>(</TT>List.tl<CODE> </CODE>result<TT>)</TT><CODE> </CODE>;;<BR><CODE>- : bool = false</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc46"></A>
<H3> The Imperative Side</H3>Let us continue the previous example, and modify a string in the list
<TT>result</TT>. 


<PRE><BR># <TT>(</TT>List.hd<CODE> </CODE>result<TT>)</TT><CODE>.[</CODE><CODE>1</CODE><CODE>]</CODE><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>'s'</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># result<CODE> </CODE>;;<BR><CODE>- : string list = ["ose"; "two"; "three"]</CODE><BR># example<CODE> </CODE>;;<BR><CODE>- : string list = ["ose"; "two"; "three"]</CODE><BR>

</PRE>

Evidently, this operation has modified the list <TT>example</TT>.
Hence, it is necessary to know the physical structure of the two
lists being manipulated, as soon as we use imperative aspects of the
language. <BR>
<BR>
Let us now observe how the order of evaluating the arguments of a
function can amount to a trap in an imperative program. We define a mutable list structure with
primitive functions for creation, modification, and access:


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>ilist<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>c<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>list<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type 'a ilist = { mutable c: 'a list }</CODE><BR># <B>let</B><CODE> </CODE>icreate<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[]<CODE> </CODE>}<BR><CODE> </CODE><B>let</B><CODE> </CODE>iempty<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>l<CODE>.</CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[]<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><B>let</B><CODE> </CODE>icons<CODE> </CODE>x<CODE> </CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>y<CODE>.</CODE>c<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>x::y<CODE>.</CODE>c<CODE> </CODE>;<CODE> </CODE>y<BR><CODE> </CODE><B>let</B><CODE> </CODE>ihd<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.hd<CODE> </CODE>x<CODE>.</CODE>c<BR><CODE> </CODE><B>let</B><CODE> </CODE>itl<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE>.</CODE>c<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>List.tl<CODE> </CODE>x<CODE>.</CODE>c<CODE> </CODE>;<CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val icreate : unit -&gt; 'a ilist = &lt;fun&gt;</CODE><BR><CODE>val iempty : 'a ilist -&gt; bool = &lt;fun&gt;</CODE><BR><CODE>val icons : 'a -&gt; 'a ilist -&gt; 'a ilist = &lt;fun&gt;</CODE><BR><CODE>val ihd : 'a ilist -&gt; 'a = &lt;fun&gt;</CODE><BR><CODE>val itl : 'a ilist -&gt; 'a ilist = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>imap<CODE> </CODE>f<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>iempty<CODE> </CODE>l<CODE> </CODE><B>then</B><CODE> </CODE>icreate()<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>icons<CODE> </CODE><TT>(</TT>f<CODE> </CODE><TT>(</TT>ihd<CODE> </CODE>l<TT>)</TT><TT>)</TT><CODE> </CODE><CODE> </CODE><TT>(</TT>imap<CODE> </CODE>f<CODE> </CODE><TT>(</TT>itl<CODE> </CODE>l<TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val imap : ('a -&gt; 'b) -&gt; 'a ilist -&gt; 'b ilist = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Despite having reproduced the general form of the 
<TT>map</TT> of the previous paragraph, with 
<TT>imap</TT> we get a distinctly different result:


<PRE><BR># <B>let</B><CODE> </CODE>example<CODE> </CODE><CODE>=</CODE><CODE> </CODE>icons<CODE> </CODE><CODE>"one"</CODE><CODE> </CODE><TT>(</TT>icons<CODE> </CODE><CODE>"two"</CODE><CODE> </CODE><TT>(</TT>icons<CODE> </CODE><CODE>"three"</CODE><CODE> </CODE><TT>(</TT>icreate()<TT>)</TT><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val example : string ilist = {c=["one"; "two"; "three"]}</CODE><BR># imap<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<TT>)</TT><CODE> </CODE>example<CODE> </CODE>;;<BR><CODE>Uncaught exception: Failure("hd")</CODE><BR>

</PRE>
<BR>
<BR>
What has happened? Just that the evaluation of <TT>(</TT>itl<CODE> </CODE>l<TT>)</TT> has
taken place before the evaluation of <TT>(</TT>ihd<CODE> </CODE>l<TT>)</TT>, so that on
the last iteration of <TT>imap</TT>, the list referenced by
l became the empty list before we examined its head. 
The list <TT>example</TT> is henceforth definitely empty even though we have not obtained any result: 


<PRE><BR># example<CODE> </CODE>;;<BR><CODE>- : string ilist = {c=[]}</CODE><BR>

</PRE>
<BR>
<BR>
The flaw in the function <TT>imap</TT> arises from a mixing of the
genres that has not been controlled carefully enough. The choice of
order of evaluation has been left to the system. We can reformulate
the function <TT>imap</TT>, making explicit the order of evaluation,
by using the syntactic construction
<B>let .. in ..</B> 


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>imap<CODE> </CODE>f<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>iempty<CODE> </CODE>l<CODE> </CODE><B>then</B><CODE> </CODE>icreate()<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>let</B><CODE> </CODE>h<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ihd<CODE> </CODE>l<CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><CODE> </CODE>icons<CODE> </CODE><TT>(</TT>f<CODE> </CODE>h<TT>)</TT><CODE> </CODE><CODE> </CODE><TT>(</TT>imap<CODE> </CODE>f<CODE> </CODE><TT>(</TT>itl<CODE> </CODE>l<TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val imap : ('a -&gt; 'b) -&gt; 'a ilist -&gt; 'b ilist = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>example<CODE> </CODE><CODE>=</CODE><CODE> </CODE>icons<CODE> </CODE><CODE>"one"</CODE><CODE> </CODE><TT>(</TT>icons<CODE> </CODE><CODE>"two"</CODE><CODE> </CODE><TT>(</TT>icons<CODE> </CODE><CODE>"three"</CODE><CODE> </CODE><TT>(</TT>icreate()<TT>)</TT><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val example : string ilist = {c=["one"; "two"; "three"]}</CODE><BR># imap<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<TT>)</TT><CODE> </CODE>example<CODE> </CODE>;;<BR><CODE>- : string ilist = {c=["one"; "two"; "three"]}</CODE><BR>

</PRE>
<BR>
<BR>
However, the original list has still been lost:


<PRE><BR># example<CODE> </CODE>;;<BR><CODE>- : string ilist = {c=[]}</CODE><BR>

</PRE>
<BR>
<BR>
Another way to make the order of evaluation explicit is to use the
sequencing operator and a looping structure.


<PRE><BR># <B>let</B><CODE> </CODE>imap<CODE> </CODE>f<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>l_res<CODE> </CODE><CODE>=</CODE><CODE> </CODE>icreate<CODE> </CODE>()<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>while</B><CODE> </CODE>not<CODE> </CODE><TT>(</TT>iempty<CODE> </CODE>l<TT>)</TT><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ignore<CODE> </CODE><TT>(</TT>icons<CODE> </CODE><TT>(</TT>f<CODE> </CODE><TT>(</TT>ihd<CODE> </CODE>l<TT>)</TT><TT>)</TT><CODE> </CODE>l_res<TT>)</TT><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ignore<CODE> </CODE><TT>(</TT>itl<CODE> </CODE>l<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>l_res<CODE> </CODE><B>with</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.rev<CODE> </CODE>l_res<CODE>.</CODE>c<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val imap : ('a -&gt; 'b) -&gt; 'a ilist -&gt; 'b ilist = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>example<CODE> </CODE><CODE>=</CODE><CODE> </CODE>icons<CODE> </CODE><CODE>"one"</CODE><CODE> </CODE><TT>(</TT>icons<CODE> </CODE><CODE>"two"</CODE><CODE> </CODE><TT>(</TT>icons<CODE> </CODE><CODE>"three"</CODE><CODE> </CODE><TT>(</TT>icreate()<TT>)</TT><TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val example : string ilist = {c=["one"; "two"; "three"]}</CODE><BR># imap<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<TT>)</TT><CODE> </CODE>example<CODE> </CODE>;;<BR><CODE>- : string ilist = {c=["one"; "two"; "three"]}</CODE><BR>

</PRE>

The presence of <TT>ignore</TT> emphasizes the fact that it is not the
result of the functions that counts here, but their side effects on
their argument. In addition, we had to put the elements of the result
back in the right order (using the function <TT>List.rev</TT>). <BR>
<BR>
<A NAME="toc47"></A>
<H3> Recursive or Iterative</H3> 
People often mistakenly associate recursive with functional and
iterative with imperative. A purely functional program cannot be
iterative because the value of the condition of a loop never varies.
By contrast, an imperative program may be recursive: the 
original version of the 
function <TT>imap</TT> is an example. <BR>
<BR>
Calling a function conserves the values of its arguments during its
computation. If it calls another function, the latter conserves its
own arguments in addition. These values are conserved on the
execution stack. When the call returns, these values are
popped from the stack. The memory space available for the stack being
bounded, it is possible to encounter the limit when using a recursive
function with calls too deeply nested. In this case, Objective CAML raises
the exception 
<TT>Stack_overflow</TT>.
<A NAME="@fonctions131"></A><BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>succ<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>else</B><CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>+</CODE><CODE> </CODE>succ<CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val succ : int -&gt; int = &lt;fun&gt;</CODE><BR># succ<CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>Stack overflow during evaluation (looping recursion?).</CODE><BR>

</PRE>
<BR>
<BR>
In the iterative version <TT>succ_iter</TT>, the stack space needed
for a call does not depend on its argument. 


<PRE><BR># <B>let</B><CODE> </CODE>succ_iter<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>j<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>n<CODE> </CODE><B>do</B><CODE> </CODE>incr<CODE> </CODE>i<CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>!</CODE>i<CODE> </CODE>;;<BR><CODE>val succ_iter : int -&gt; int = &lt;fun&gt;</CODE><BR># succ_iter<CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>- : int = 100001</CODE><BR>

</PRE>
<BR>
<BR>
The following recursive version has <EM>a priori</EM> the same depth of
calls, yet it executes successfully with the same argument. 


<PRE><BR># <B>let</B><CODE> </CODE>succ_tr<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>succ_aux<CODE> </CODE>n<CODE> </CODE>accu<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE>accu<CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>succ_aux<CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>accu<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>succ_aux<CODE> </CODE><CODE>1</CODE><CODE> </CODE>n<CODE> </CODE>;;<BR><CODE>val succ_tr : int -&gt; int = &lt;fun&gt;</CODE><BR># succ_tr<CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>- : int = 100001</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="rec-term"></A>
<A NAME="@concepts109"></A>
This function has a special form of recursive call, called tail
recursion, in which the result of this call will be the result of the
function without further computation. It is therefore unnecessary to
have stored the values of the arguments to the function while
computing the recursive call. When Objective CAML can observe that a call
is tail recursive, it frees the arguments on the stack before making
the recursive call. This optimization allows recursive functions that
do not increase the size of the stack. <BR>
<BR>
Many languages detect tail recursive calls, but it is indispensable in a functional language, where naturally many
tail recursive calls are used. <BR>
<BR>
<HR>
<A HREF="book-ora036.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora038.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
